import random


def fermat_prime(n):
    return 2 ** (2 ** n) + 1


def generate_keypair():
    # Генерация двух простых чисел
    p = random.randint(100, 1000)
    q = random.randint(100, 1000)

    while not is_prime(p):
        p = random.randint(100, 1000)

    while not is_prime(q) or q == p:
        q = random.randint(100, 1000)

    n = p * q  # Вычисление модуля
    phi = (p - 1) * (q - 1)  # Вычисление функции Эйлера

    # Выбор открытой экспоненты e (обычно выбирают простое число)
    e = fermat_prime(random.randint(0, 5))

    # Вычисление закрытой экспоненты d
    d = int(pow(e, -1, phi))

    return ((n, e), (n, d))


def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True


def encrypt(message, public_key):
    n, e = public_key
    cipher_text = [pow(ord(char), e, n) for char in message]
    return cipher_text


def decrypt(cipher_text, private_key):
    n, d = private_key
    decrypted_text = [chr(pow(char, d, n)) for char in cipher_text]
    return ''.join(decrypted_text)


# Генерация ключей
public_key, private_key = generate_keypair()

# Сообщение для шифрования
message = (input("Введите текст: "))

# Шифрование
cipher_text = encrypt(message, public_key)
print("Зашифрованное сообщение:", cipher_text)

# Расшифрование
decrypted_text = decrypt(cipher_text, private_key)
print("Расшифрованное сообщение:", decrypted_text)
